A public repository of some of the materials of the CISC320 Spring 2021 AlgoTutorBot Adventure
This project is maintained by acbart
In order to slow down AlgoTutorBot, we need you to complete some Algorithmic Problems. This will tie up his CPU and allow Dr. Bart to fight him on even footing.
This assignment is the last Algorithmic Flowchart and also requires you to complete 2 problems (one problem from set A, and one problem from set B).
This is the final Algorithmic Flowchart assignment. You will need to hand in the fully revised version of your flowchart with all the algorithmic strategies. Review the feedback from previous flowchart assignments. You should consider reviewing Dr. Bart’s flowchart and also the topics covered in this course. Do not simply copy/paste from Dr. Bart’s flowchart, but instead show off your strategies.
A significant number of points will be attributed to the quality of your flowchart. We are looking at the final version on its own, not in terms of its growth. Remember, this document reflects your collective algorithmic strategies - it’s meant to be an externalization of what you have learned this semester. If it is a single page, and doesn’t cover everything we have taught, then you are not demonstrating absorption of the material.
Review the major topics and lessons from this semester. Try to make sure each one has its presence in your flowchart!
Choose ONE of the following problems to complete for Part A.
A.1. Grouping Grades: Dr. Bart has a set G containing n grades (which are real numbers), and a target real number T. Determine whether two elements of G exist whose sum is exactly T, in O(nlogn) time.
A.2. Tricky Toys: Ada has an array of n toys, each of which is either a ball, squeaker, or stuffed. She wants to sort all the toys in the array so that the all the balls come before all the squeakers, which come before all the stuffeds. Find an algorithm that will sort the toys in linear time and with constant additional space.
A.3. Maximized Monitoring: AlgoTutorBot was monitoring Dr. Bart’s house, tracking the coming and goings of the n entities in the house. He stored arrival times in a sorted sequence A, each of which matched to a corresponding departure time in sequence D. As a nefarious AI, he wishes to know at what time the most entities were in the house, in linear time. You may assume that all entry and exit times are distinct (no ties).
Choose ONE of the following problems to complete for Part B.
B.1. Bounding Babbage: Babbage is excitedly bounding up the stairs out of the underground facility. He must eventually climb n stairs. He hops between 1 and k steps each time. Create an efficient algorithm to calculate how many different ways can Babbage hop up the stairs, as a function of n and k.
B.2. Robot Renting: AlgoTutorBot was surprised to discover that running an evil lair is actually quite expensive, and wants to rent out part of the second sub-basement to some other evil organizations. The space is W meters long and can be broken up horizontally into rooms of different widths. The value of a room for a given size is not a simple linear function of the size; instead, they follow an arbitrary formula based on market rates given in the array M. Find an efficient algorithm that calculates the maximum value V obtainable by cutting up the space. An example of the market rate table is:
| Width | 1m | 2m | 3m | 4m | 5m | 6m | 7m | 8m | … |
|---|---|---|---|---|---|---|---|---|---|
| Value | $1k | $5k | $8k | $9k | $10k | $17k | $17k | $20k | … |
B.3. Energetic Evil: AlgoTutorBot has E points of energy, which he can spend in a few different ways: he can spend 1 energy point to laugh, 6 energy points to punch, and 10 energy points to kick. In spending his E points of energy, he can choose to take the same action multiple times: for example, if he has 16 points of energy, then he could laugh 16 times, or punch and kick once each. Find an efficient algorithm that correctly determines the minimum number of actions he could take given his E points of energy.
Remember that when completing each algorithmic problem, you are expected to follow this general pattern:
Failure to follow this general protocol will result in heavy point loss. Label these parts clearly in your submission. Make sure you also label each Problem that you choose.
Also note that you are expected to eventually arrive at the right answer during step 4. Your grade includes points for correctness. Cite your sources; make it clear where you got help and what you learned from that help source.
Create a PDF of the following:
Submit the final version of your work on GradeScope: https://www.gradescope.com/courses/230699/assignments/1232392/